//
// Created by Dell on 2021/11/29.
//

#include <iostream>
#include <math.h>
using namespace std;

int calN(int n,int p){
    int ans = 0;
    while(n){
        ans += n/p;
        n/=p;
    }
    return ans;
}
typedef  long long ll;
long long res[67][67] = {0};
long long calC(ll n,ll m){
    if(m == 0 || n == m ){ return  1;}
    if(res[n][m]) return res[n][m];
    else return res[n][m] = calC(n-1,m) + calC(n-1,m-1);
}

const int n = 20;
void calC2(){
    for(int i = 0;i<=n;++i){
        res[i][0] = res[i][i] = 1;
    }
    for(int i = 2;i<=n;++i){
        for(int j = 0;j<= i/2;++j){
            res[i][j] = res[i-1][j] + res[i-1][j-1];
            res[i][i-j] = res[i][j];
        }
    }
}

ll calC3(ll n,ll m){
    ll ans = 1;
    for(ll i =1;i<=m;++i){
        ans = ans * (n-m+i)/i; // 一定要先乘再除
    }
    return ans;
}

const int maxn = 1e6;
int prime[maxn],pNum= 0;// 存素数
bool p[maxn] = {false};// 判断是不是合数
void AiShiPrimeInit(){
    for(int i = 2;i<maxn;++i){
        if(p[i] == false){
            prime[pNum++] = i;
            for(int j = 2*i;j<maxn;j+=i){
                p[j] = true;
            }
        }
    }
}

int binaryPow(int a,int b,int p){
    int ans = 1;
    while(b){
        if(b&1) ans = (ans * a)%p;
        b = b >> 1;
        a = (a * a )%p;
    }
    return ans%p;
}
int calC_P(int n,int m,int p){
    AiShiPrimeInit();
    int ans = 1;
    for(int i = 0;prime[i] <= n;++i){
        int c = calN(n,prime[i]) - calN(m,prime[i]) - calN(n-m,prime[i]);
        ans = ans * binaryPow(prime[i],c,p)%p;
    }
    return ans;
}


int main(){

    printf("%d\n",calN(10,2));
//    printf("%d", calC(5,4));
    calC2();
    printf("%d\n", res[5][4]);
    cout<<calC3(5,4)<<endl;
    cout<<calC_P(5,4,3);
    return 0;
}